package com.zhz.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 389. 找不同
 * <p>
 * 给定两个字符串 s 和 t，它们只包含小写字母。
 * 字符串 t由字符串 s 随机重排，然后在随机位置添加一个字母。
 * 请找出在 t中被添加的字母。
 * <p>
 * 示例 1：
 * 输入：s = "abcd", t = "abcde"
 * 输出："e"
 * 解释：'e' 是那个被添加的字母。
 * <p>
 * 示例 2：
 * 输入：s = "", t = "y"
 * 输出："y"
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-the-difference
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindTheDifference389 {

    public static void main(String[] args) {
        FindTheDifference389 m = new FindTheDifference389();
        char tmp = m.findTheDifference("aaae", "aaaae");
        System.out.println(tmp);
    }

    /**
     * 使用hashMap来解
     * 注意，可以有重复的字符串  比如s ="aa"   t="aaa"
     */
    public char findTheDifference(String s, String t) {
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char m : s1) {
            if (map.containsKey(m)) {
                map.put(m, map.get(m) + 1);
            } else {
                map.put(m, 1);
            }
        }
        for (int j = 0; j < t1.length; j++) {
            char a = t1[j];
            if (!map.containsKey(a)) {
                return t.charAt(j);
            } else {
                int count = map.get(a);
                if (count == 0) {
                    return a;
                } else {
                    map.put(a, count - 1);
                }
            }
        }
        return '0';
    }

    /**
     * 使用异或来解决
     * 异或：如果相同则会变为0，并且可以移动   比如2^3^2   则可以重新排列  (2^2)^3
     * <p>
     * 不要使用String.charAt()进行查找  这样查找的时间复杂度较高
     */
    public char findTheDifference1(String s, String t) {
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        int tmp = 0;
        for (int i = 0; i < s1.length; i++) {
            tmp ^= s1[i];
            tmp ^= t1[i];
        }
        return (char) (tmp ^ t1[t1.length - 1]);
    }


}
